The present invention relates to databases, and more specifically, to performing index scans in databases. A database index is a data structure that improves the speed of data retrieval operations on a database table, at the cost of slower writes and increased storage space. Indexes can be created using one or more columns of a database table, providing the basis for both rapid random lookups and efficient access of ordered records. The disk space required to store the index is typically less than that required by the table (since indices usually contain only the key-fields according to which the table is to be arranged, and exclude all the other details in the table), yielding the possibility to store indices in memory for a table whose data is too large to store in memory.
If no index exists on a table, a table scan must be performed for each table referenced in a database query. The larger the table, the longer a table scan takes because a table scan requires each table row to be accessed sequentially. Although a table scan might be more efficient for a complex query that requires most of the rows in a table, for a query that returns only some table rows an index scan can access table rows more efficiently. Typically an optimizer of the database system determines to perform an index scan if the index columns are referenced in the SELECT statement and if the optimizer estimates that an index scan will be faster than a table scan. Index files generally are smaller and require less time to read than an entire table, particularly as tables grow larger. In addition, the entire index may not need to be scanned. The predicates that are applied to the index reduce the number of rows to be read from the data pages.
The performance of index scan methods is very sensitive to the synchronous input/output operations (I/Os) that occur during the scans. As a result, there are many approaches to prefetching the required pages into the bufferpool before the scanning transaction needs them, such that synchronous waits for the I/O to complete can be avoided.
Some of the existing prefetching methods include sequential prefetching and index non-leaf to leaf prefetching. In sequential prefetching, ranges of pages are read into the bufferpool. Thus, the sequential prefetching method is dependent upon the leaves of the index being well clustered. In the index non-leaf to leaf prefetching method, the non-leaf page in the index is used to prefetch only the leaves that are needed for an index scan. While there are several methods to prefetching pages, the decision of which prefetching method to use is typically done at bind time (that is, query compilation time), or at run time, based solely upon whether sequences of pages are (mostly) in clustering order. This is also referred to as dynamic prefetching.
However, there are some cases where these traditional prefetching methods fall short. One such case is when sequential prefetching is chosen at query compilation time, but the clustering of the object changes so that a sequential prefetching is no longer beneficial, for example, when the index leaf pages become unclustered as a result of insert and delete activity. Dynamic prefetching attempts to remedy this, but unfortunately the dynamic prefetching only detects when the pages are in near sequential order so that sequential prefetching can be used. With the advent of newer prefetching mechanisms, it becomes desirable to have more elaborate detection methods to determine when prefetching is desirable, and which methods to use. Additionally, it becomes desirable to have methods that adjust to changing conditions within an index, as it is very common for the clustering and bufferpool residency characteristics of an index to change throughout the index.